package com.hdu.hot100.tree;

import java.util.HashMap;
import java.util.Map;

public class lc105 {


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {

        Map<Integer, Integer> num2indexMapping;

        public TreeNode buildTree(int[] preorder, int[] inorder)
        {
            num2indexMapping = createNum2IndexMapping(inorder);
            return doBuild(preorder, 0, preorder.length - 1, 0, preorder.length - 1);
        }

        TreeNode doBuild(int[] preorder, int il, int ir, int pl, int pr)
        {
            if (il > ir || pl > pr)
            {
                return null;
            }
            else if (il == ir || pl == pr)
            {
                return new TreeNode(preorder[pl]);
            }
            else
            {
                int rootVal = preorder[pl];
                int rootIndex = num2indexMapping.get(rootVal);
                /**
                 * [il, rootIndex - 1] rootIndex [rootIndex + 1, ir]
                 *
                 * [pl] [pl + 1 , x] [x + 1, pr]
                 *
                 * x - pl - 1 = rootIndex - 1 - il
                 * x = pl + rootIndex - il
                 */
                int x = pl + rootIndex - il;
                TreeNode root = new TreeNode(rootVal);
                root.left = doBuild(preorder, il, rootIndex - 1, pl + 1, x);
                root.right = doBuild(preorder, rootIndex + 1, ir, x + 1, pr);
                return root;
            }
        }

        Map<Integer, Integer> createNum2IndexMapping(int[] inorder)
        {
            Map<Integer, Integer> num2index = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) {
                num2index.put(inorder[i], i);
            }
            return num2index;
        }
    }
}
